package com.atguigu.sort;

import java.util.Arrays;
import java.util.Random;
/*
* 选择排序  n2    不稳定：外层循环从前往后，该位置的数和后面的数进行比较，小的放到这个位置上面
* 冒泡排序  n2    稳定  ：外层循环从前往后，内层选择两个数两两比较，大的往后挪动
* 插入排序  n2    稳定  ：外层循环从前往后，内层从1开始，和前面的数进行比较，小的往前挪动
*   堆排序  nlogn 不稳定：我们首先对一个无序的数组变成一个大顶锥，就是对于非叶子节点使其变成大于左右节点的数字，从length/2开始，直到0。
*                        然后我们把大顶锥的数和数组最后一个交换，直到结束
* 快速排序  nlogn 不稳定：我们选取一个作为基准，然后把数组分成两部分，一部分比这个基准大，一部分比这个基准小，然后left和这个基准替换，
*                        这个基准数字就放到了他的最终位置，对这个两部分分别进行这个操作，我们的快速排序就完成了。
* 归并排序  nlogn 稳定  ：我们的思想是对两个有序的数组进行组合成一个有序的数组
* 希尔排序  n1.3  不稳定：我们以一定的间隔距离对其进行排序，然后缩小这个间距，直到间距为1，我们的数组就排序好了
*   桶排序  n+k   稳定  ：
* 计数排序  n+k   稳定  ：这个不是基于比较的思想，而是对于一定范围内的大量的重复数字进行排序，我们先设定好我们每个相同的数字一定有多少个
*                        然后从1开始添加后面的数字我们可以确定的count i对应的数字最大值就是这个数字在数组中的最后的位置，然后--count[i]
* 基数排序  n*k   稳定  ：这个也不是基于比较的思想，然后里面最大的数的长度，然后根据个十百。。。的数字进行大小比较，然后放入到数组中，
*                        和计数排序的做法差不多。
*
* */
public class DataChecker {
    static int[] generateRandomArray(){
        Random random = new Random();
        int[] arr=new int[10000];
        for (int i=0;i<arr.length;i++){
            arr[i]=random.nextInt(10000);
        }
        return arr;
    }
    static String check(){
        boolean same=true;
        int[] arr=generateRandomArray();
        int[] arr_copy=new int[arr.length];
        System.arraycopy(arr,0,arr_copy,0,arr.length);
        Arrays.sort(arr);
        //使用我们的排序方法进行排序
//        BubbleSort.sort(arr_copy);
//        SelectionSort.sort(arr_copy);
//        InsertionSort.sort(arr_copy);
//        ShellSort.sort(arr_copy);
//        QuickSort.sort(arr_copy);
//        CountSort.sort(arr_copy);
//        RadixSort.sort(arr_copy);
//        MergeSort.sort(arr_copy);
        HeapTreeSort.sort(arr_copy);
        for (int i = 0; i < arr.length; i++) {



            if(arr[i]!=arr_copy[i]){
                same=false;
                break;
            }
        }
        String res= same==true?"right":"wrong";
        return res;

    }
    static void cycle(){
        int right_num=0;
        for (int i = 0; i < 100; i++) {
            String res= check();
            if(res=="right") {
                right_num++;
            }
        }
        System.out.println("100次中共有"+right_num+"次正确");
    }

    public static void main(String[] args) {
        cycle();
    }

}
